package q233_countDigitOne;

public class Solution {

    /*
    此题主要是针对数学问题的考验
    我们以为1234567为例 依次考虑每一个位置上会出现多少次1
    假设当前到达百位 如果百位出现1 那么只有 100 - 199 这一段会出现
    并且是每1000就会出现一次 100 - 199 的循环
    所以是每过1000，百位置上就会出现100个1
    1234567有1234个1000 所以有1234 * 100 个 1 会出现
    而对于剩下的567
    则需要考虑剩下的数字大小 如果剩下的是0 - 100 则没有1
    100 - 200 则会出现 (n % 1000) - 100 + 1个1
    200以上则也是100个1
    所以就得到了每个位置上出现1的个数的一个通用公式
    (n / (mul_k * 10)) * mul_k + Math.min(Math.max(n % (mul_k * 10) - mul_k + 1, 0), mul_k);
     */
    public int countDigitOne(int n) {
        long mul_k = 1;
        int ans = 0;

        while (n >= mul_k) {
            ans += (n / (mul_k * 10)) * mul_k + Math.min(Math.max(n % (mul_k * 10) - mul_k + 1, 0), mul_k);
            mul_k *= 10;
        }
        return ans;
    }
}
